package algorithms.leecode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Au79 {
    public static void main(String[] args) {
        Map m = new HashMap();

        System.err.println(new Au79().exist(new char[][]{
                {'A','B','C','E'},
                {'S','F','E','S'},
                {'A','D','E','E'}
        },
        "ABCESEEEFS"));

    }

    public boolean exist(char[][] board, String word) {
        if (board.length == 0) {
            return false;
        }

        // 第一个点匹配
        int x = board.length;
        int y = board[0].length;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (board[i][j] == word.charAt(0)) {
                    boolean[][] bArr = new boolean[board.length][board[0].length];
                    bArr[i][j] = true;
                    if( ext(board,i,j,1,word,bArr)) return true;
                    // 第一个点不匹配
                } else {
                    boolean[][] bArr = new boolean[board.length][board[0].length];
                    if (ext(board,i,j,0,word,bArr)) return true;
                }
            }
        }
return false;
    }

//    public boolean ext1(char[][] board,int xIndex,int yIndex,int wIndex,String word) {
//        while (!ext(board,xIndex,yIndex,0,word)) {
//
//        }
//    }

    public boolean ext(char[][] board,int xIndex,int yIndex,int wIndex,String word, boolean[][] bArr) {
        // 右边移动
        if (wIndex == word.length()) {
            return true;
        }
        if (xIndex == board.length) {
            return false;
        }
        // 下
        if (move(board,xIndex + 1,yIndex,word.charAt(wIndex),bArr)) {
            if (ext(board,xIndex + 1,yIndex,wIndex+1,word,bArr)){
                return true;
            }

        }
        // 左
        if (move(board,xIndex ,yIndex - 1,word.charAt(wIndex),bArr)){
            if(ext(board,xIndex ,yIndex - 1,wIndex+1,word,bArr)){
                return true;
            }

        }
        // 上
        if (move(board,xIndex -1 ,yIndex ,word.charAt(wIndex),bArr)){
            if( ext(board,xIndex - 1,yIndex ,wIndex+1,word,bArr)){
                return true;
            }
        }
        // 右
        if (move(board,xIndex,yIndex+1,word.charAt(wIndex),bArr)) {
            if( ext(board,xIndex,yIndex+1,wIndex+1,word,bArr)){
                return true;
            }

        }
        bArr[xIndex][yIndex] = false;
        return false;
    }
    public boolean move(char[][] board, int xIndex,int yIndex,char x, boolean[][] bArr) {


        if (yIndex < 0 || xIndex < 0) {
            return false;
        }
        if (board.length == xIndex) {
            return false;
        }
        // 当前行越界
        if (board[xIndex].length <= yIndex) {
            return false;
        }

        // 当前纵越界
        if (bArr[xIndex][yIndex]) {
            return false;
        }
        if (board[xIndex][yIndex] == x) {

            bArr[xIndex][yIndex] = true;
            return true;
        }
        return false;
    }
}
